Các thông tin về sự giàu có của Malacca thu hút sự chú ý của Manuel I, vua của Bồ Đào Nha và ông đã gửi Đô đốc Diogo Lopes de Sequeira để tìm Malacca, sau đó thiết lập cho một công ty thương mại với người đứng đầu của nó như là người đại diện tại Đông Ấn thuộc Bồ Đào Nha. Người châu Âu đầu tiên đến Malacca và Đông Nam Á, Sequeira thăm Malacca vào năm 1509. Mặc dù lúc đầu ông được đón tiếp bởi Sultan Mahmud Shah. Tuy nhiên, rác rối nhanh chóng đến sau đó[1]. Sự cạnh tranh giữa Hồi giáo và Kitô giáo được thuật lại bởi một nhóm người Hồi giáo từ Goa, sau khi Goa bị chiếm đóng bởi Bồ Đào Nha[2]. Cộng đồng hồi giáo quốc tế thuyết phục Mahmud tin rằng Bồ Đào Nha là một mối đe dọa nghiêm trọng. Mahmud ra lệnh bắt giữ, thủ tiêu một số người Bồ Đào Nha và cố gắng tấn công bốn tàu Bồ Đào Nha, mặc dù bốn tàu này đã trốn thoát được. Kinh nghiệm mà người Bồ Đào Nha đã học được từ Ấn Độ, một cuộc phạt là cách duy nhất để thiết lập cai trị ở Malacca[1].

Vào tháng 4 năm 1511, Afonso de Albuquerque rời cảng Goa đến Malacca với một lực lượng gồm 1,200 người và mười bảy hay mười tám tàu.[1] Các chỉ huy ra một số yêu sách, một trong số đó là được cho phép là xây dựng một pháo đài của Bồ Đào Nha gần nơi giao thương của thành phố.[2] Sultan từ chối tất cả các yêu sách. Xung đột không thể tránh khỏi và sau 40 ngày chiến đấu, Malacca bị đánh bại bởi Bồ Đào Nha vào ngày 24 tháng 08. Một cuộc tranh chấp gay gắt giữa Sultan Mahmud và con trai của ông Sultan Ahmad càng làm suy yếu Malaccan.[1]

Sau thất bại của Vương quốc Malacca vào ngày 15 tháng 08 năm 1511, Bồ Đào Nha chiếm được Malacca. Afonso de Albuquerque đã tìm cách xây dựng một pháo đài kiên cố với dự đoán đủ để chống đỡ các cuộc phản công từ Sultan Mahmud. Một pháo đài được thiết kế và xây dựng bao gồm một ngọn đồi, dọc theo mép bờ biển, ở phía đông nam của cửa sông, trên nền cũ mà trước đây là cung điện của nhà vua. Albuquerque vẫn ở Malacca cho đến tháng 11 năm 1511 và chuẩn bị phòng thủ chống lại bất kỳ phản kháng nào của người Malay[1]. Sultan Mahmud Shah đã buộc phải chạy trốn khỏi Malacca.